Ch.1 Linear Systems and Gauss's Method

Return to TOC

Systems of Linear Equations

Chemistry Example

Balancing xCX7HX8+yHNOX3→zCX7HX5OX6NX3+wHX2O\ce{xC7H8 + yHNO3 -> zC7H5O6N3 + wH2O}

{7x=7z8x+y=5z+2wy=3z3y=6z+w\begin{cases} 7x=7z\\8x+y=5z+2w\\y=3z\\3y=6z+w \end{cases}
From 7x=7z7x=7z, x=zx=z. From x=zx=z and y=3zy=3z, 8z+3z=5z+2w→w=3z8z+3z=5z+2w\rightarrow w=3z.
Letting z=1z=1, x=1x=1, y=3y=3, w=3w=3:
CX7HX8+3HNOX3→CX7HX5OX6NX3+3HX2O\ce{C7H8 + 3HNO3 -> C7H5O6N3 + 3H2O}

Gauss's Method

Linear Combination of x1,x2,...,xnx_1,x_2,...,x_n has form a1x1+a2x2+⋯+anxna_1x_1+a_2x_2+\cdots+a_nx_n, where a1,...,an∈Ra_1,...,a_n\in\mathbb{R} are coefficients

Example 1.1

.5x−y+z.5x-y+z is an example
xy+zxy+z is not

Linear Equation is in form a1x1+a2x2+⋯+anxn=da_1x_1+a_2x_2+\cdots+a_nx_n=d where d∈Rd\in\mathbb{R} is the constant.
nn-tuple (s1,s2,...,sn)(s_1,s_2,...,s_n) satisfies the equation when a1s1+a2s2+⋯+ansn=da_1s_1+a_2s_2+\cdots+a_ns_n=d, and is called the solution
System of Linear Equation has several linear equations
a1,1x1+a1,2x2+⋯+a1,nxn=d1⋮an,1x1+an,2x2+⋯+an,nxn=dna_{1,1}x_1+a_{1,2}x_2+\cdots+a_{1,n}x_n=d_1\\\vdots\\a_{n,1}x_1+a_{n,2}x_2+\cdots+a_{n,n}x_n=d_n
nn-tuple (s1,s2,...,sn)(s_1,s_2,...,s_n) must satisfy all equations

Row operators: arrow with expression above like ρ1+ρ2\rho_1+\rho_2 or ρ1↔ρ2\rho_1\leftrightarrow\rho_2
put the row in which operators act on at the end (some books put it at the start)

Leading variable: first variable with a nonzero coefficient
echelon form: the leading variable is to the right of the previous equation's leading variable
x+4y−4z=0−11y+7z=36z=12\begin{array}{rrrrrl}x&+&4y&-&4z&=&0\\ &&-11y&+&7z&=&3\\ &&&&6z&=&12 \end{array}

Theorem:

the following operators does not change the set of solutions

  1. an equation is swapped with another (swapping)
  2. an equation has both sides multiplied by a nonzero constant (rescaling)
  3. an equation is replaced by the sum of itself and a multiple of another (row combination)
    called elementary reduction operations, row operations, or Gaussian operations

An inconsistency (like 0=−10=-1) gives no solutions, an obvious fact (like 0=00=0) gives infinitely many solutions, and fewer equations than variables also gives infinitely many solutions

Example 1.2

Convert the following system of equations to echelon form:
3x−4y+2z=−112x−y+z=−3−x+2y+3z=13\begin{array}{rrrrrrr} 3x&-&4y&+&2z&=&-11\\ 2x&-&y&+&z&=&-3\\ -x&+&2y&+&3z&=&13 \end{array}

3x−4y+2z=−112x−y+z=−3−x+2y+3z=13→2ρ3+ρ13ρ3+ρ12y+11z=283y+7z=23−x+2y+3z=13→ρ1↔ρ3\begin{array}{rrrrrrr}3x&-&4y&+&2z&=&-11\\ 2x&-&y&+&z&=&-3\\ -x&+&2y&+&3z&=&13 \end{array} \xrightarrow[2\rho_3+\rho_1]{3\rho_3+\rho_1} \begin{array}{rrrrrrr} &&2y&+&11z&=&28\\ &&3y&+&7z&=&23\\ -x&+&2y&+&3z&=&13 \end{array} \xrightarrow[]{\rho_1\leftrightarrow\rho_3}
−x+2y+3z=132y+11z=283y+7z=23→−3/2ρ2+ρ3−x+2y+3z=132y+11z=28−19/2z=−19\begin{array}{rrrrrrr} -x&+&2y&+&3z&=&13\\ &&2y&+&11z&=&28\\ &&3y&+&7z&=&23 \end{array} \xrightarrow[]{-3/2\rho_2+\rho_3} \begin{array}{rrrrrrr} -x&+&2y&+&3z&=&13\\ &&2y&+&11z&=&28\\ &&&&-19/2z&=&-19 \end{array}

Describing the Solution Set

parametrize by free variables, variables that are not leading in echelon form
2x+y+z−w=5−y+z+4w=6\begin{array}{rrrrrrrrr} 2x&+&y&+&z&-&w&=&5\\ &-&y&+&z&+&4w&=&6 \end{array}
Free variables are zz and ww, parametrize in terms of those and constants
y=−6+z+4wx=12(5−y−z+w)=112−z−32wy=-6+z+4w\\ x=\frac{1}{2}(5-y-z+w)=\frac{11}{2}-z-\frac{3}{2}w

Example 1.3

Find the solution set to the following system of equations:
2x+y−5z−3w=4−x+3y−8z+5w=−9\begin{array}{rrrrrrrr}2x&+&y&-&5z&-&3w&=&4\\-x&+&3y&-&8z&+&5w&=&-9\end{array}

2x+y−5z−3w=4−x+3y−8z+5w=−9→ρ1↔ρ22ρ2+ρ1−x+3y−8z+5w=−97y−21z+7w=−14→1/7ρ2−ρ1x−3y+8z−5w=9y−3z+w=−2\begin{array}{rrrrrrrr}2x&+&y&-&5z&-&3w&=&4\\-x&+&3y&-&8z&+&5w&=&-9\end{array}\\ \xrightarrow[\rho_1\leftrightarrow\rho_2]{2\rho_2+\rho_1}\begin{array}{rrrrrrrr}-x&+&3y&-&8z&+&5w&=&-9\\&&7y&-&21z&+&7w&=&-14\end{array}\\ \xrightarrow[1/7\rho_2]{-\rho_1}\begin{array}{rrrrrrrr}x&-&3y&+&8z&-&5w&=&9\\&&y&-&3z&+&w&=&-2\end{array}
The free variables are zz and ww, and yy can be parametrized in terms of them.
y=3z−w−2y=3z-w-2
Now, substitute yy and solve xx in terms of zz and ww
x−3(3z−w−2)+8z−5w=9→x−z−2w+6=9x=z+2w+3x-3(3z-w-2)+8z-5w=9\xrightarrow{} x-z-2w+6=9\\ x=z+2w+3
So, the solutions are
x=z+2w+3y=3z−w−2x=z+2w+3\\y=3z-w-2

Matrices

m×nm\times n matrix has mm rows and nn columns
(a1,1a1,2⋯a1,j⋯a1,n⋮⋮⋮⋮⋮⋮ai,1ai,2⋯ai,j⋯ai,n⋮⋮⋮⋮⋮⋮am,1am,2⋯am,j⋯am,n)\begin{pmatrix}a_{1,1} & a_{1,2} & \cdots & a_{1,j} & \cdots & a_{1,n}\\\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\a_{i,1}&a_{i,2}&\cdots&a_{i,j}&\cdots&a_{i,n}\\\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\a_{m,1}&a_{m,2}&\cdots&a_{m,j}&\cdots&a_{m,n}\end{pmatrix}
also denoted (ai,j)i=1,...,mj=1,...,n(a_{i,j})_{\substack{i=1,...,m\\j=1,...,n}}
ai,ja_{i,j} is element in row ii and column jj

Vector

column vector, or just vector, is a matrix with a single column
single row vector called row vector
Column Vector: v⃗=(−1−0.50)\vec{v}=\begin{pmatrix}-1\\-0.5\\0\end{pmatrix}
Row Vector: w⃗=(−1−0.50)\vec{w}=\begin{pmatrix}-1 & -0.5 & 0\end{pmatrix}

Vector Sum: u⃗+v⃗=(u1⋮un)+(v1⋮vn)=(u1+v1⋮un+vn)\vec{u}+\vec{v}=\begin{pmatrix}u_1\\\vdots\\u_n\end{pmatrix}+\begin{pmatrix}v_1\\\vdots\\v_n\end{pmatrix}=\begin{pmatrix}u_1+v_1\\\vdots\\u_n+v_n\end{pmatrix}
Scalar Multiplication: rv⃗=r(v1⋮vn)=(rv1⋮rvn)r\vec{v}=r\begin{pmatrix}v_1\\\vdots\\v_n\end{pmatrix}=\begin{pmatrix}rv_1\\\vdots\\rv_n\end{pmatrix}

Turn linear system into matrix AA and column vector d⃗\vec{d}
A=(a1,1a1,2⋯a1,n⋮⋮⋮⋮am,1am,2⋯am,n)and d⃗=(d1⋮dm)A=\begin{pmatrix}a_{1,1}&a_{1,2}&\cdots&a_{1,n}\\\vdots&\vdots&\vdots&\vdots\\a_{m,1}&a_{m,2}&\cdots&a_{m,n}\end{pmatrix} \text{and } \vec{d}=\begin{pmatrix}d_1\\\vdots\\d_m\end{pmatrix}
Converting to column matrices, the linear system can be written
x1a⃗1+x2a⃗2+⋯+xna⃗n=d⃗x_1\vec{a}_1+x_2\vec{a}_2+\cdots+x_n\vec{a}_n=\vec{d}
where
a⃗k=(a1,k⋮am,k)\vec{a}_k=\begin{pmatrix}a_{1,k}\\\vdots\\a_{m,k}\end{pmatrix}

Augmented Matrix

combines matrix AA and column vector d⃗\vec{d} into one matrix
(A∣d⃗)=(a1,1a1,2⋯a1,j⋯a1,nd1⋮⋮⋮⋮⋮⋮⋮ai,1ai,2⋯ai,j⋯ai,ndi⋮⋮⋮⋮⋮⋮⋮am,1am,2⋯am,j⋯am,ndm)(A|\vec{d})=\left(\begin{array}{cccccc|c}a_{1,1} & a_{1,2} & \cdots & a_{1,j} & \cdots & a_{1,n}&d_{1}\\\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\a_{i,1}&a_{i,2}&\cdots&a_{i,j}&\cdots&a_{i,n}&d_i\\\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\a_{m,1}&a_{m,2}&\cdots&a_{m,j}&\cdots&a_{m,n}&d_m\end{array}\right)

Use row reduction on an augmented matrix to simplify the process of solving linear systems

Parametrized solutions can be written in vector notation
e.g.
{(xyz)=(1/310)+z(2/34/31)|z∈R}\left\{\begin{pmatrix}x\\y\\z\end{pmatrix}=\begin{pmatrix}1/3\\1\\0\end{pmatrix}+z\begin{pmatrix}2/3\\4/3\\1\end{pmatrix}\middle|z\in\mathbb{R}\right\}

Example 1.4

The following linear system
2x1+3x2−4x3+x4=−12−x1−2x2+4x3−2x4=9−3x1+x2−3x4=−3x2−3x4=−62x_1+3x_2-4x_3+x_4=-12\\-x_1-2x_2+4x_3-2x_4=9\\-3x_1+x_2-3x_4=-3\\x_2-3x_4=-6
can be turned into the matrix and column vector
A=(23−41−1−24−2−310−3010−3)d⃗=(−129−3−6)\begin{array}{cc}A=\begin{pmatrix}2&3&-4&1\\-1&-2&4&-2\\-3&1&0&-3\\0&1&0&-3\end{pmatrix}\vec{d}=\begin{pmatrix}-12\\9\\-3\\-6\end{pmatrix}\end{array}
The matrix AA can be split into column matrices, so the linear system can also be written
x1(2−1−30)+x2(3−211)+x3(−4400)+x4(1−2−3−3)=(−129−3−6)x_1\begin{pmatrix}2\\-1\\-3\\0\end{pmatrix}+x_2\begin{pmatrix}3\\-2\\1\\1\end{pmatrix}+x_3\begin{pmatrix}-4\\4\\0\\0\end{pmatrix}+x_4\begin{pmatrix}1\\-2\\-3\\-3\end{pmatrix}=\begin{pmatrix}-12\\9\\-3\\-6\end{pmatrix}

In augmented matrix form, this looks like
(23−41−12−1−24−29−310−3−3010−3−6)\left(\begin{array}{cccc|c}2&3&-4&1&-12\\-1&-2&4&-2&9\\-3&1&0&-3&-3\\0&1&0&-3&-6\end{array}\right)
The system can be solved by applying row reduction to the augmented matrix
(23−41−12−1−24−29−310−3−3010−3−6)→−ρ4+ρ3(23−41−12−1−24−29−30003010−3−6)→ρ1↔1/−3ρ3(1000−1−1−24−2923−41−12010−3−6)→−2ρ1+ρ3ρ1+ρ2(1000−10−24−2803−41−10010−3−6)→ρ4↔ρ2(1000−1010−3−603−41−100−24−28)→2ρ2+ρ4−3ρ2+ρ3(1000−1010−3−600−4108004−8−4)→ρ3+ρ4(1000−1010−3−600−410800024)Echelon Form\begin{array}{rccc} &\left(\begin{array}{cccc|c}2&3&-4&1&-12\\-1&-2&4&-2&9\\-3&1&0&-3&-3\\0&1&0&-3&-6\end{array}\right)&\xrightarrow{-\rho_4+\rho_3}&\left(\begin{array}{cccc|c}2&3&-4&1&-12\\-1&-2&4&-2&9\\-3&0&0&0&3\\0&1&0&-3&-6\end{array}\right)\\ \\ \xrightarrow{\rho_1\leftrightarrow1/-3\rho_3}&\left(\begin{array}{cccc|c}1&0&0&0&-1\\-1&-2&4&-2&9\\2&3&-4&1&-12\\0&1&0&-3&-6\end{array}\right)&\xrightarrow[-2\rho_1+\rho_3]{\rho_1+\rho_2}&\left(\begin{array}{cccc|c}1&0&0&0&-1\\0&-2&4&-2&8\\0&3&-4&1&-10\\0&1&0&-3&-6\end{array}\right)\\ \\ \xrightarrow{\rho_4\leftrightarrow\rho_2}&\left(\begin{array}{cccc|c}1&0&0&0&-1\\0&1&0&-3&-6\\0&3&-4&1&-10\\0&-2&4&-2&8\end{array}\right)&\xrightarrow[2\rho_2+\rho_4]{-3\rho_2+\rho_3}&\left(\begin{array}{cccc|c}1&0&0&0&-1\\0&1&0&-3&-6\\0&0&-4&10&8\\0&0&4&-8&-4\end{array}\right)\\ \\ \xrightarrow{\rho_3+\rho_4}&\begin{array}{c}\left(\begin{array}{cccc|c}1&0&0&0&-1\\0&1&0&-3&-6\\0&0&-4&10&8\\0&0&0&2&4\end{array}\right)\\\text{Echelon Form}\end{array}&& \end{array}
This is equivalent to the linear system
x1=−1x2−3x4=−6−4x3+10x4=82x4=4\begin{array}{rrrrrrrrr}x_1&&&&&&&=&-1\\&&x_2&&&&-3x_4&=&-6\\&&&&-4x_3&+&10x_4&=&8\\&&&&&&2x_4&=&4\end{array}
From row 4,
x4=2x_4=2
From row 3,
−4x3+10(2)=8→x3=3-4x_3+10(2)=8\rightarrow x_3=3
From row 2,
x2−3(2)=−6→x2=0x_2-3(2)=-6\rightarrow x_2=0
From row 1,
x1=−1x_1=-1
So, the solution is
(x1x2x3x4)=(−1032)\begin{pmatrix}x_1\\x_2\\x_3\\x_4\end{pmatrix}=\begin{pmatrix}-1\\0\\3\\2\end{pmatrix}